#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) Huoty, All rights reserved
# Author: Huoty <sudohuoty@163.com>
# CreateTime: 2020-07-04 17:23:47


def topo_sort(graph):
    in_degrees = dict((u, 0) for u in graph)  # 每个节点的入度
    for u in graph:  # 计算每个节点的入度
        for v in graph[u]:
            in_degrees[v] += 1

    q = [u for u in graph if in_degrees[u] == 0]  # 找出一个入度为 0 的节点
    s = []
    while q:
        u = q.pop()  # 默认从最后一个移除
        s.append(u)
        for v in graph[u]:  # 同时移除其指向
            in_degrees[v] -= 1

            if in_degrees[v] == 0:
                q.append(v)

    if len(s) == len(graph):
        return s
    else:
        return None  # 当输出序列与图节点数不相同时，说明图有环，不存在拓扑排序


if __name__ == "__main__":
    graph = {
        'a': 'bf',
        'b': 'cdf',
        'c': 'd',
        'd': 'ef',
        'e': 'f',
        'f': ''
    }
    print(topo_sort(graph))
